package com.zlsy.learning.leetcode.binarysearch;

/**
 * @author zhouliang
 * @date 2020/9/17 14:56
 */
public class BsearchDemo1 {

  public static void main(String[] args) {
    int[] arr = new int[] {8, 11, 19, 23, 27, 33, 45, 55, 67, 98};
    int n = arr.length;
    int value = 23;
    //    int bsearch = bsearch1(arr, n, value);
    int low = 0;
    int high = n - 1;
    int i = bsearchInternally(arr, low, high, value);
    System.out.println(i);
    //    System.out.println(bsearch);
  }

  /**
   * 简单的二分查找示例 O(logN)
   *
   * @param a a数组
   * @param n 数组长度
   * @param value 要查找的值
   * @return int
   */
  private static int bsearch(int[] a, int n, int value) {
    int low = 0;
    int high = n - 1;
    while (low <= high) {
      int mid = (low + high) / 2;
      if (a[mid] == value) {
        return mid;
      } else if (value < a[mid]) {
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    }
    return -1;
  }

  private static int bsearch1(int[] a, int n, int value) {
    int low = 0;
    int high = n - 1;
    while (low <= high) {
      // n >> 1 = n/2;
      int mid = low + ((high - low) >> 1);
      if (a[mid] == value) {
        return mid;
      } else if (value < a[mid]) {
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    }
    return -1;
  }

  private static int bsearchInternally(int[] a, int low, int high, int value) {
    if (low > high) {
      return -1;
    }
    int mid = low + ((high - low) >> 1);
    if (a[mid] == value) {
      return mid;
    } else if (a[mid] > value) {
      return bsearchInternally(a, low, mid - 1, value);
    } else {
      return bsearchInternally(a, mid + 1, high, value);
    }
  }
}
